package com.sentiment.algorithm;

/**
 * Created by vani:liaozhenlin on 15-4-14.
 * If you meet any question,you can email at 939899727@qq.com
 *
 * @author 廖贞林  from uestc
 */
public class Kmp {
    private int patternLength;
    private String pattern;
    private String text;
    private int textLength;
    private int next[];
    public Kmp(String text,String pattern){
        this.pattern=new String(pattern);
        this.text=new String(text);
        patternLength=pattern.length();
        textLength=text.length();
        next=new int[patternLength];
        getNext();
    }

    private void getNext(){
        next[0]=-1;
        int k=-1,i=0;
        while (i<patternLength-1){
            if(k!=-1&&pattern.charAt(k)!=pattern.charAt(i)){
                k=next[k];
            }
            k++;i++;
            if(pattern.charAt(k)==pattern.charAt(i)){
                next[i]=next[k];
            }else {
                next[i]=k;
            }
        }
//        for(int j=0;j<patternLength-1;j++){
//            System.out.print(next[j]+",");
//        }
//        System.out.println(next[patternLength-1]);
    }

    public int kmpSelf(){
        if("".equals(text)||"".equals(pattern)){
            return -1;
        }
//        getNext();
        int index=0,i=0,j=0;
        while(i<textLength-1&&j<patternLength-1){
            if(text.charAt(i)==pattern.charAt(j)){
                i++;j++;
            }else {
                index+=j-next[j];
                if(next[j]!=-1){
                    j=next[j];
                }else {
                    j=0;i++;
                }
            }
        }

        if(j==patternLength-1){
            return index;
        }else {
            return -1;
        }
    }

    public static void main(String[] args){
        Kmp kmp=new Kmp("我和d金额和花胡而","金额和");
        System.out.println(kmp.kmpSelf());

    }
}
